package dmsxl.dongtaiguihua;

/**
 * Author: Zhang Dongwei
 * Date: 2023/7/22 20:28
 * 给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
 * 你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
 * 请你计算并返回达到楼梯顶部的最低花费。
 */
public class dtgh4_746 {

    public static void main(String[] args) {
//        int[] cost = {1, 100, 1, 1, 1, 100, 1, 1, 100, 1};
//        int[] cost = {10, 15, 20};
        int[] cost = {1, 100};
        System.out.println(minCostClimbingStairs(cost));
    }

//    自己写的，效果还好
    public static int minCostClimbingStairs1(int[] cost) {
        int[] dp = new int[cost.length + 1];
        dp[0] = 0;
        dp[1] = 0;
        for (int i = 2; i <= cost.length; i++){
            dp[i] = Math.min((dp[i-1] + cost[i-1]),(dp[i-2] + cost[i-2]));
        }
        return dp[cost.length];
    }
//    自己写的进阶版
    public static int minCostClimbingStairs(int[] cost) {
        int a = 0;
        int b = 0;
        int sum = 0;
        for (int i = 2; i <= cost.length; i++){
            sum = Math.min((b + cost[i-1]),(a + cost[i-2]));
            a = b;
            b = sum;
        }
        return sum;
    }
}
